package week01

import "math"

// 53. 最大子序和
// https://leetcode-cn.com/problems/maximum-subarray/

//
// 1、求前缀和
// 2、固定r，维护r之前最小前缀和

const IntMax = int(^uint(0) >> 1) // 首位0，后面全是1
const IntMin = ^IntMax // 首位1，后面全是0

func maxSubArray(nums []int) int {
	var sums = make([]int, len(nums)+1)
	for i := 1; i <= len(nums); i++ {
		sums[i] = sums[i-1] + nums[i-1]
	}
	var preMin, ans = sums[0], IntMin
	for i := 1; i <= len(nums); i++ {
		ans = max(ans, sums[i] - preMin)
		preMin = min(preMin, sums[i])
	}
	return ans
}

func min(x, y int) int {
	return int(math.Min(float64(x), float64(y)))
}

func max(x, y int) int {
	return int(math.Max(float64(x), float64(y)))
}